package xyz.zhuht.algorithm.difficult;

/**
 * @author haitao zhu
 * @date 2020/5/24 15:40
 * 4.寻找两个正序数组的中位数
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 * <p>
 * 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * <p>
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * nums1 = [1, 3]
 * nums2 = [2]
 * <p>
 * 则中位数是 2.0
 * 示例 2:
 * <p>
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * <p>
 * 则中位数是 (2 + 3)/2 = 2.5
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class XunZhaoLiangGeZhengXuShuZuDeZhongWeiShu {
  public static void main(String[] args) {
    int[] nums1 = new int[]{1, 2};
    int[] nums2 = new int[]{3,4};
    System.out.println(findMedianSortedArrays(nums1, nums2));
  }

  public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) {
      int[] temp = nums1;
      nums1 = nums2;
      nums2 = temp;
    }

    int m = nums1.length;
    int n = nums2.length;

    // 分割线左边的所有元素需要满足的个数 m + (n - m + 1) / 2;
    int totalLeft = (m + n + 1) / 2;

    // 在 nums1 的区间 [0, m] 里查找恰当的分割线，
    // 使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]
    int left = 0;
    int right = m;

    while (left < right) {
      int i = left + (right - left + 1) / 2;
      int j = totalLeft - i;
      if (nums1[i - 1] > nums2[j]) {
        // 下一轮搜索的区间 [left, i - 1]
        right = i - 1;
      } else {
        // 下一轮搜索的区间 [i, right]
        left = i;
      }
    }

    int i = left;
    int j = totalLeft - i;
    int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
    int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
    int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
    int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

    if (((m + n) % 2) == 1) {
      return Math.max(nums1LeftMax, nums2LeftMax);
    } else {
      return (double) ((Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2;
    }
  }
}
